package FindtheDuplicateNumber;

public class Solution {
	public int findDuplicate(int[] nums) {
		int left = 1, right = nums.length - 1;
		boolean[] bo = new boolean[nums.length];
		while (left + 1 < right) {
			int mid = (left + right) / 2;
			int up = 0, down = 0, eq = 0;
			for (int i = 0; i < nums.length; i++)
				if (bo[i]==false) {
					if (nums[i] > mid)
						up++;
					else if (nums[i] <= mid)
						down++;
					if (nums[i] == mid)
						eq++;
				}
			if (eq > 1)
				return (int) mid;
			if (down <= (mid-left)+1) {
				left=mid;
				for (int i = 0; i < nums.length; i++)
					if (nums[i] < mid)
						bo[i] = true;
			} else {
				right=mid;
				for (int i = 0; i < nums.length; i++)
					if (nums[i] > mid)
						bo[i] = true;
			}
		}
		int count=0;
		for (int i = 0; i < nums.length; i++)
			if (nums[i]==left) count++;
		if (count>1) return (int) left;
		return (int) right;
	}
	public static void main(String args[]) {
		Solution so=new Solution();
		int[] t={13,17,11,18,9,19,15,7,14,3,16,15,15,15,15,10,2,6,12,15};
		System.out.println(so.findDuplicate(t));
		
	}
}
